package main

import "fmt"

type tree struct {
	value       int
	left, right *tree
}

func sort(values []int) {
	var root *tree
	for _, v := range values {
		root = add(root, v)
	}
	appendValue(values[:0], root)
}

// appendValue 将元素按照顺序追加到 values 里面， 然后返回结果 slice
func appendValue(values []int, t *tree) []int {
	if t != nil {
		values = appendValue(values, t.left)
		values = append(values, t.value)
		values = appendValue(values, t.right)
	}
	return values
}

func add(t *tree, value int) *tree {
	if t == nil {
		//等价于返回 &tree{value: value}
		t = new(tree)
		t.value = value
		return t
	}
	if value < t.value {
		t.left = add(t.left, value)
	} else {
		t.right = add(t.right, value)
	}
	return t
}

func main() {
	a := []int{123, 23, 3, 342, 13, 5, 2, 13}
	sort(a)
	fmt.Println(a)
}
